package com.集合.Map___.HashTable___;

import java.util.Hashtable;
@SuppressWarnings("all")
public class HashTable_底层源码 {
    public static void main(String[] args) {
        /**
         * HashTable  HashMap 区别
         * 效率 HashMap > HashTable
         * 线程安全性 HashTable（安全）   HashMap（不安全）
         * HashMap 允许存放Null
         * HashTable 不允许存放Null
         */
        Hashtable ht = new Hashtable();
        for (int i = 0; i < 12; i++) {
            ht.put(new A(i), i);
        }
        System.out.println(ht);
    }
}

class A{
    int a;

    public A(int a) {
        this.a = a;
    }

    @Override
    public int hashCode() {
        return 30;
    }


    public String toString() {
        return a+"";
    }
}

@SuppressWarnings("all")
/**
 * 底层源码
 *
 * 模拟HashTable的添加，扩容机制；   事先将A类的Hash Code重写，固定成一个数，为了让这些对象形成链表；
 *
 * 初始化HashTable;  （初始化为11，临界比例为0.75）
 * 1.Hashtable ht = new Hashtable();
 *      public Hashtable() {
 *         this(11, 0.75f);  初始容量11，临界比例0.75；
 *         即 初始化容量和临界容量（当前容量*临界比例0.75 = 11*0.75 = 8），当数量超过8个时就开始扩容；
 *     }
 *
 *      public Hashtable(int initialCapacity, float loadFactor) {
 *         if (initialCapacity < 0)    //当初始容量 <0 就抛出异常
 *             throw new IllegalArgumentException("Illegal Capacity: "+  initialCapacity);
 *         if (loadFactor <= 0 || Float.isNaN(loadFactor))     //当临界比例《=0 就抛出异常
 *             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
 *
 *         if (initialCapacity==0)  如果初始容量=0，就初始化为1；
 *             initialCapacity = 1;
 *         this.loadFactor = loadFactor;    //初始化临界比例；
 *         table = new Entry<?,?>[initialCapacity];    //创建长度为11的Entry数组给到Table
 *         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
 *           //初始化临界容量（当前容量*临界比例0.75 = 11*0.75 = 8），即：当数量超过8个时就开始扩容；，
 *     }
 *
 *添加元素  （挂到链表头）
 * 2.ht.put(new A(i), i);
 *      if (value == null) {  //如果value == null 抛出空指针异常；
 *             throw new NullPointerException();
 *         }
 *          Entry<?,?> tab[] = table;    //将数组给到临时数组tab
 *         int hash = key.hashCode();    //获取hash值；
 *         int index = (hash & 0x7FFFFFFF) % tab.length;  //计算该对象的hash值对应的坐标索引；
 *         Entry<K, V> entry = (Entry<K,V>)tab[index];  //取出当前坐标的对象；
 *         for(; entry != null ; entry = entry.next) {  //如果当前对象不为空，即 已经存在对象；
 *             if ((entry.hash == hash) && entry.key.equals(key)) {
 *                 V old = entry.value;    //如果hash值一样并且内容也一样的话，返回当前位置的value并用传进来的替换原来的；
 *                 entry.value = value;
 *                 return old;
 *             }
 *         }
 *
 *         addEntry(hash, key, value, index);  如果没有相同的就添加；
 *         return null;
 *     }
 *     //添加模块
 *      private void addEntry(int hash, K key, V value, int index) {
 *         Entry<?,?> tab[] = table;   //临时数组tab
 *         if (count >= threshold) {
 *             // 如果当前元素数量超过了临界容量 就扩容，重新分配空间 （对哈希表进行重新哈希，以扩大容量并减少冲突，从而保持哈希表的高效性能。）
 *             rehash();  //扩容方法；
 *
 *             tab = table;
 *             hash = key.hashCode();  //扩容完后重新计算hash对应的索引；
 *             index = (hash & 0x7FFFFFFF) % tab.length;
 *         }
 *
 *         // Creates the new entry.
 *         Entry<K, V> e = (Entry<K,V>) tab[index];  //将当前索引位置的元素取出来给到 e
 *         tab[index] = new Entry<>(hash, key, value, e);
 *         //创建新的Entry对象，把当前位置的原对象 e 放到新对象的下一个节点，把新对象放到当前索引
 *         即：把新的元素接到当前链表的头（如果当前位置有元素一样，如果没有，该放哪儿就放哪儿）；
 *         count++;
 *         modCount++;
 *     }
 *
 *
 *3.扩容机制  （新容量 = 当前容量*2 +1 ）
 *
 * protected void rehash() {
 *         int oldCapacity = table.length;  //获取原长度
 *         Entry<?,?>[] oldMap = table;  //原数组
 *
 *         // overflow-conscious code
 *         int newCapacity = (oldCapacity << 1) + 1;   //新容量 = 原容量*2 +1
 *         if (newCapacity - MAX_ARRAY_SIZE > 0) {   //无关紧要的if
 *             if (oldCapacity == MAX_ARRAY_SIZE)
 *                 // Keep running with MAX_ARRAY_SIZE buckets
 *                 return;
 *             newCapacity = MAX_ARRAY_SIZE;
 *         }
 *
 *         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];   //创建新的数组长度为11*2 +1 = 23
 *
 *         modCount++;
 *         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);   //重新设置临界容量23*0.75 = 17
 *         table = newMap;    //将创建好的数组给到原来table数组
 *
 *         for (int i = oldCapacity ; i-- > 0 ;) {  //把旧数组的元素遍历，重新计算分配分配空间；（从尾巴开始）
 *             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
 *                 Entry<K,V> e = old; //当前元素不为空 ， 把当前元素 old 给到临时变量 e
 *                 old = old.next;  //为了下一个节点不丢掉，也拿到该链表的下一个节点
 *
 *                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;  //重新计算索引；
 *                 e.next = (Entry<K,V>)newMap[index];  //将新的索引的元素取出来接到e的下一个节点
 *                 newMap[index] = e;  //把 e放到该元素的位置  即：如果当前位置有元素，就放到前面，原来的挂到后面
 *             }
 *         }
 *     }
 *
 *
 * 示意图
 * 2.演示添加；
 * 分别添加 1，2，3，4，5，6,7,8
 * （1） 1->null
 * （2） 2->1->null
 * （3） 3->2->1->null
 * （4） 4->3->2->1->null  以此类推； 8->7->6->5->4->3->2->1->null
 *
 * 演示扩容
 * 3.再添加一个 9 就会超过临界值，触发扩容机制，（先扩容再添加）  （自己规定hash值一样，会放到一个链表，重新计算后也是一样的）
 *      （只描述一个链表上的重新分配：原来的链表8->7->6->5->4->3->2->1->null）
 * 1.   （1.）先将该链表的第一个取出 （8）放到新的节点（假如当前位置为null）
 *      将8放到链表头 即 ：8->null
 *      (2)再取出下一个节点 7 放到链表头 即： 7->8->null
 *      (3)再取出下一个节点 6 放到链表头 即： 6->7->8->null
 *      ......取出最后一个节点元素1 放到链表头 即： 1->2->3->4->5->6->7->8->null
 * 2.扩容重新分配完了后再添加新的的元素 9
 * （1）假如计算后索引还是一样，跟之前添加一样放到链表头 即：9->1->2->3->4->5->6->7->8->null
 *  (2)再添加一个元素10 同理：10->9->1->2->3->4->5->6->7->8->null
 *
 */
class b{};//没有用

